The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Crashing is shortening the project makespan by reducing activity times in a project network by allocating resources to them. Activity durations are often uncertain and an exact probability distribution itself might be ambiguous. We study a class of distributionally robust project crashing problems where the objective is to optimize the first two marginal moments (means and SDs) of the activity durations...
In the context of the Firefighter problem, a deterministic model of the spread of a fire or virus on a graph, SFIRE is the decision problem that asks if a specified set of vertices can be prevented from burning. We show SFIRE remains NP‐complete even when restricted to graphs with maximum degree 3 even when the fire starts at a vertex of degree 2.
We study gas network problems with compressors and control valves under uncertainty that can be formulated as two‐stage robust optimization problems. Uncertain data are present in the physical parameters of the pipes as well as in the overall demand. We show how to exploit the special decomposable structure of the problem to reformulate the two‐stage problem as a single‐stage robust optimization problem...
The vitality of an arc/node of a graph with respect to the maximum flow between two fixed nodes s and t is defined as the reduction of the maximum flow caused by the removal of that arc/node. In this paper, we address the issue of determining the vitality of arcs and/or nodes for the maximum flow problem. We show how to compute the vitality of all arcs in a general undirected graph by solving only...
In this article we propose a new single‐source shortest‐path algorithm that achieves the same O(n · m) time bound as the Bellman‐Ford‐Moore algorithm but outperforms it and other state‐of‐the‐art algorithms in many cases in practice. Our claims are supported by experimental evidence.
A rainbow cycle in an undirected edge‐colored graph is a cycle in which all edges have different colors. A rainbow cycle cover of a graph is a set of disjoint rainbow cycles, where each vertex belongs to exactly one cycle. The objective of the rainbow cycle cover problem is to minimize the number of rainbow cycles used to cover the vertices of the graph while the trivial cycle version also keeps the...
In this work we introduce and study the strong generalized minimum label spanning tree (GMLST), a novel optimization problem defined on edge‐labeled graphs. Given a label set associated to each edge of the input graph, the aim is to look for the spanning tree using the minimum number of labels. Differently from the previously introduced GMLST problem, including a given edge in the solution means that...
In this paper we study a network design problem arising in the management of a carrier network. The aim is to route a traffic matrix, minimizing a measure of the network congestion while guaranteeing a prescribed quality of service. We formulate the problem, devise presolve procedures to reduce the size of the corresponding mixed‐integer programming formulation and show that the proposed approach...
The optimal diversity management problem (ODMP) arises in many application fields when a company, producing a good and/or a service customizable with options, has to satisfy many different client demands with various subset of options, but only a limited number of option combinations can be produced. ODMP can be represented by a disconnected network and formulated as a large‐scale ‐median problem...
This paper addresses a variant of the minimum spanning tree problem in which, given a list of conflicting edges, the primary goal is to find a spanning tree with the minimum number of conflicting edge pairs and the secondary goal is to minimize the weight of spanning trees without conflicts. The problem is NP‐hard and it finds applications in the design of offshore wind farm networks. We propose a...
In this paper we face a distribution problem arising in a freight logistics context. More precisely, we are involved with the containerized flow originating from maritime terminals and going to inland destinations using the road transportation network. The goal is the minimization of the total shipping costs, given by the travelled distance, vehicles and external cost components. In particular, we...
The capacitated edge activation problem consists of activating a minimum cost set of capacitated edges to ensure the routing of some traffic demands. If the demands are subject to uncertainty, we speak of the robust capacitated edge activation problem. We consider a capacity formulation of the problem and investigate, from a polyhedral perspective, the similarities and the differences between the...
A basic question in network analysis concerns the quantification of the importance of each node in terms of network connectivity. To this end, a possible approach consists in using cooperative game theory tools to define a measure of node centrality. In this paper, given a transportation network, a cooperative game model with transferable utility (TU game) is considered. The nodes of the network represent...
The objective of this paper is to develop a monotonicity theory for the important class of minimum convex‐cost parametric multicommodity network‐flow problems defined over directed graphs. The results allow us to determine when it is possible to predict, without numerical computations, the direction of change of optimal multicommodity flows resulting from changes in arc‐commodity parameters. In particular,...
We study a class of vehicle‐routing problems with simultaneous pickup and delivery (VRPSPD). In VRPSPDs, each customer may require a certain quantity of goods delivered from the depot and a quantity of goods to be picked up and returned to the depot. Besides the standard VRPSPD, we address (1) the VRPSPD with time limit (VRPSPDTL), which imposes a time limit on the routes of the transportation vehicles,...
We study a variant of the shortest path problem in a congested environment. In this setting, the travel time of each arc is represented by a piecewise continuous affine function of departure time. Besides, the driver is allowed to wait at nodes to avoid wasting time in traffic. While waiting, the driver is able to perform useful tasks for her job or herself, so the objective is to minimize only driving...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.